// 单向链表类
class LinkedList {
  head = null;
  length = 0;
  constructor() { }

  // 添加一个新节点在链表尾部
  append(element) {
    // 1.创建一个新的节点类
    const newNode = new Node(element);
    let temporaryNode = this.head;
    // 2.判断是否存在head指向
    //  1) 存在:    循环遍历, 依次赋值, 使用一个临时变量"temporaryNode"存储每次循环的next, 直到next为null, 将"newNode"赋值给temporaryNode.next
    //  2) 不存在:  将head指向此节点
    if (temporaryNode) {
      while (temporaryNode.next) temporaryNode = temporaryNode.next;
      temporaryNode.next = newNode;
    } else {
      this.head = newNode;
    }
    // 3.链表长度+1
    this.length++;
  }

  // 添加新节点 支持任意位置插入数据
  insert(position, element) {
    // 1.下标越界处理
    if (position < 0) return false;
    const MaxIndex = this.length - 1;
    if (position > MaxIndex) position = MaxIndex;
    const newNode = new Node(element);
    // 2.存储第一个head 用于遍历访问
    let temporaryNode = this.head;
    if (position === 0) {
      // 3.head替换
      newNode.next = temporaryNode;
      temporaryNode = newNode;
    } else {
      // 4.找出指定位置的元素节点
      // i = 1 是为了减少一次遍历次数 因为第一个head已经取出来了
      for (let i = 1; i < position; i++) temporaryNode = temporaryNode.next;
      // 5.将指定位置节点的next赋值给当前插入元素的next
      // 6.将插入元素赋值给指定位置节点的next
      newNode.next = temporaryNode.next;
      temporaryNode.next = newNode;
    }
    // 7.长度++
    this.length++;
    return true;
  }

  // 老师的方法
  insertTeacher(position, element) {
    // 1.对position进行越界判断
    if (position < 0 || position > this.length) return false;

    // 2.创建插入节点
    const newNode = new Node(element);

    // 3.判断插入位置是否为第一个
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let index = 0;
      let currentNode = this.head;
      // 插入节点位置的上一个节点
      let prevNode = null;
      while (index++ < position) {
        prevNode = currentNode;
        currentNode = currentNode.next;
      }
      newNode.next = prevNode.next;
      prevNode.next = newNode;
    }

    // 4.长度++
    this.length++;
    return true;
  }

  // 获取对应下标的元素信息
  get(position) {
    if (position >= this.length || position < 0) return null;
    let index = 0;
    let currentNode = this.head;
    while (index++ < position) currentNode = currentNode.next;
    return currentNode.element;
  }

  // 查找对应元素下标
  indexOf(element) {
    if (!this.length) return -1;
    let index = 0;
    let currentNode = this.head;
    while (currentNode) {
      if (element === currentNode.element) return index;
      currentNode = currentNode.next;
      index++;
    }
    return -1;
  }

  // 修改某个位置元素节点的数据
  update(position, element) {
    // 1.越界判断
    if (position >= this.length || position < 0) return false;
    // 2.查找正确的节点
    let index = 0;
    let currentNode = this.head;
    while (index++ < position) currentNode = currentNode.next;
    // 3.修改元素
    currentNode.element = element;
    return true;
  }

  // 删除链表中指定位置的元素节点
  removeAt(position) {
    // 1.越界判断
    if (position >= this.length || position < 0) return false;
    let index = 0;
    let currentNode = this.head;
    if (position == 0) {
      this.head = this.head?.next;
    } else {
      // 2.找到这个节点的上一个元素
      while (index++ < position - 1) currentNode = currentNode.next;
      // 跳过目标节点 直接链接下一个节点即可
      currentNode.next = currentNode.next.next;
    }
    // 3.长度--
    this.length--;
    return true;
  }

  // 删除链表中指定元素的元素节点
  remove(element) {
    // TODO: 非常鲁棒 哈哈哈哈哈~
    return this.removeAt(this.indexOf(element));
  }

  // 判断链表是否为空
  isEmpty() {
    return this.length === 0;
  }

  // 返回链表长度
  size() {
    return this.length;
  }

  // 将链表所有节点的数据取出 拼接成一个字符串
  toString() {
    let temporaryNode = this.head;
    let temporaryList = [];
    while (temporaryNode) {
      temporaryList.push(temporaryNode.element);
      // 下一个链表
      temporaryNode = temporaryNode.next;
    }
    return temporaryList.join(" ");
  }
}

// 节点类
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

const linked = new LinkedList();

// 添加一些数据
linked.append(123);
linked.append("Mr.chen");
linked.append(456);

// 在第一个元素后面插入一个元素
// linked.insert(1, "测试1");
// linked.insert(10, "测试2");
// linked.insertTeacher(1, "测试1");
console.log("toString: ", linked.toString());

// 测试get方法
console.log(linked.get(1));
console.log(linked.get(2));
console.log(linked.get(3));

console.log(linked.indexOf(456));

console.log(linked.update(0, "我是小陈"));
console.log(linked.get(0));

// console.log(linked.removeAt(2));
console.log(linked.remove(456));

console.log("toString: ", linked.toString());

// linked.removeAt(0);
// linked.removeAt(0);

console.log(linked.size());
console.log(linked.isEmpty());